import heapq
from typing import List


class Solution:
    _MOD = 10 ** 9 + 7

    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buy_heap = []
        sell_heap = []

        for price, amount, order_type in orders:
            if order_type == 0:  # buy:买入
                while amount and sell_heap and sell_heap[0][0] <= price:
                    if sell_heap[0][1] <= amount:
                        amount -= sell_heap[0][1]
                        heapq.heappop(sell_heap)
                    else:
                        sell_heap[0][1] -= amount
                        amount = 0
                if amount:
                    heapq.heappush(buy_heap, [-price, amount])
            else:  # sell:卖出
                while amount and buy_heap and -buy_heap[0][0] >= price:
                    if buy_heap[0][1] <= amount:
                        amount -= buy_heap[0][1]
                        heapq.heappop(buy_heap)
                    else:
                        buy_heap[0][1] -= amount
                        amount = 0
                if amount:
                    heapq.heappush(sell_heap, [price, amount])

        return (sum(amount for price, amount in buy_heap) + sum(amount for price, amount in sell_heap)) % self._MOD


if __name__ == "__main__":
    print(Solution().getNumberOfBacklogOrders(orders=[[10, 5, 0], [15, 2, 1], [25, 1, 1], [30, 4, 0]]))  # 6
    print(Solution().getNumberOfBacklogOrders(
        orders=[[7, 1000000000, 1], [15, 3, 0], [5, 999999995, 0], [5, 1, 1]]))  # 999999984
